home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / a_utils / decomp.lha / decomp / hll.c < prev    next >
C/C++ Source or Header  |  1988-01-12  |  13KB  |  621 lines
  1. /*
  2.  * Module: hll.c
  3.  *
  4.  * Author: J. Reuter
  5.  *
  6.  * This module converts the tree of generic control constructs produced
  7.  * by hier() into a tree of C-specific control constructs.  It is based
  8.  * on the Unix "struct" program (which is poorly commented, so this is
  9.  * too).
  10.  */
  11.  
  12. #include "defs.h"
  13. #include "nodes.h"
  14.  
  15. #define NTYPE(v) (node_array[v]->node_type)
  16. #define REACH(v) (node_array[v]->reach)
  17. #define RSIB(v) (node_array[v]->right_sibling)
  18. #define LCHILD(v,i) (node_array[v]->child[i])
  19. #define ARCNUM(v) (node_array[v]->num_arcs)
  20. #define ARC(v,i) (node_array[v]->arcs[i])
  21. #define CHILDNUM(v) (node_info[node_array[v]->node_type].num_children)
  22.  
  23. /* lexical successor of v, for N_ITER only */
  24. #define BRK(v) (node_array[v]->varpart[V_FATHER])
  25. #define LABEL(v) REACH(v)
  26. #define NEG(v) (node_array[v]->varpart[V_NEGATE])
  27. #define NXT(v) (node_array[v]->varpart[V_NEXT])
  28. #define LPRED(v) (node_array[v]->varpart[V_LOOP_PRED])
  29.  
  30. struct pair {
  31.     int smallest;
  32.     int second;
  33. };
  34.  
  35. static int num_counter;
  36. static int *head;
  37.  
  38. hll()
  39. {
  40.     int v;
  41.  
  42.     num_counter = 0;
  43.     getreach();
  44.  
  45.     fixflow( 0, NONE );
  46.  
  47.     getthen( 0 );
  48.  
  49.     head = (int *) malloc( node_count * sizeof(int) );
  50.  
  51.     for ( v = 0; v < node_count; v++ )
  52.     head[v] = NONE;
  53.  
  54.     for ( v = 0; DEFINED(v); v = RSIB(v) )
  55.     fixhd( v, NONE );
  56.  
  57.     /* fixhd must be called before getloop so that
  58.        it gets applied to N_IF which becomes NXT(w) for N_UNTIL w */
  59.  
  60.     getloop();
  61.  
  62.     getbranch();
  63.  
  64.     free( head );
  65.     head = NULL;
  66. }
  67.  
  68. /*
  69.  * set REACH(v) = w if w is only node outside subtree of v which is
  70.  * reached from within subtree of v, REACH(v) = NONE otherwise
  71.  */
  72.  
  73. #define NUM(v) ( DEFINED(v) ? node_array[v]->node_scratch : NONE )
  74. #define SETNUM(v) (node_array[v]->node_scratch)
  75.  
  76. /* strategy in obtaining REACH(v) for each node v:
  77.  * Since only need to know whether there is exactly one exit from subtree of v,
  78.  * need keep track only of 2 farthest exits from each subtree rather than all
  79.  * exits.
  80.  * The first may be the unique exit, while the second is used when the children
  81.  * of a node has the same first exit.
  82.  * To obtain 2 farthest exits of v, look at 2 farthest exits of children of
  83.  * v and the nodes entered by arcs from v.  Farthest exits are identified
  84.  * by numbering the nodes from -2 to -(accessnum-2) starting at the bottom
  85.  * left corner of tree using procedure number().  The farthest exit from
  86.  * the subtree of v is the one with the least number according NUM to
  87.  * this numbering.  If a node w is an exit from the subtree of v, THEN_ARC
  88.  * NUM(w) < NUM(v).  The negative numbers allow NUM(v) to be stored in
  89.  * the same location as REACH(v).  REACH(w) may already be set when an
  90.  * arc (v,w) to a child is searched, but the negative numbering is
  91.  * consistent, i.e. NUM(v) < NUM(w) in this case as in other cases
  92.  * where w is not an exit from the subtree of v.
  93.  */
  94.  
  95. /* obtain REACH(v) for each node v */
  96. static
  97. getreach()
  98. {
  99.     register int v;
  100.     struct pair pair;
  101.  
  102.     for (v = 0; v < node_count; ++v)
  103.     REACH(v) = NONE;
  104.  
  105.     number( 0 );
  106.  
  107.     for (v = 0; DEFINED(v); v = RSIB(v))
  108.     exits( v, &pair );
  109. }
  110.  
  111. /*
  112.  * set REACH(v) = w if w is only node outside subtree of v which is
  113.  * reached from within subtree of v, leave REACH(v) NONE otherwise
  114.  */
  115. static
  116. exits( v, vpair )
  117. register int v;
  118. register struct pair *vpair;
  119. {
  120.     struct pair chpair;
  121.     register int w, t;
  122.     register int i;
  123.  
  124.     vpair->smallest = vpair->second = NONE;
  125.  
  126.     for ( i = 0; i < CHILDNUM(v); i++ ) {
  127.     w = LCHILD(v,i);
  128.     if (!DEFINED(w))
  129.         continue;
  130.  
  131.     for ( t = w; DEFINED(t); t = RSIB(t) ) {
  132.         exits( t, &chpair );
  133.  
  134.         /*
  135.          * set vpair->smallest,second to two smallest of vpair->smallest,
  136.          * second, chpair->smallest,second
  137.          */
  138.         if ( inspr( chpair.smallest, vpair ) )
  139.         inspr( chpair.second, vpair );
  140.     }
  141.     }
  142.  
  143.     for ( i = 0; i < ARCNUM(v); i++ ) {
  144.     w = ARC(v,i);
  145.     if (!DEFINED(w))
  146.         continue;
  147.     inspr( w, vpair );
  148.     }
  149.  
  150.     /* throw out nodes in subtree of  v */
  151.     if ( NUM( vpair->second ) >= NUM( v ) ) {
  152.     vpair->second = NONE;
  153.     if ( NUM( vpair->smallest ) >= NUM( v ) )
  154.         vpair->smallest = NONE;
  155.     }
  156.  
  157.     if ( vpair->second == NONE )
  158.     REACH(v) = vpair->smallest; /* vpair->smallest possibly NONE */
  159.     else
  160.     REACH(v) = NONE;
  161. }
  162.  
  163. /*
  164.  * number nodes from -2 to -(accessnum+2) starting at bottom left
  165.  * corner of tree
  166.  */
  167. static
  168. number( v )
  169. register int v;
  170. {
  171.     register int i;
  172.     register int w;
  173.  
  174.     for ( i = 0; i < CHILDNUM(v); i++ ) {
  175.     w = LCHILD(v,i);
  176.     if ( DEFINED(w) )
  177.         number( w );
  178.     }
  179.  
  180.     SETNUM(v) = num_counter - 2;
  181.     num_counter--;
  182.  
  183.     if ( DEFINED(RSIB(v)) )
  184.     number( RSIB(v) );
  185. }
  186.  
  187. /* insert w in order in pr, return TRUE if <= smaller of pr */
  188. /* don't insert duplicates */
  189. static int
  190. inspr( w, pr )
  191. register int w;
  192. register struct pair *pr;
  193. {
  194.     if (w == pr-> smallest)
  195.     return TRUE;
  196.  
  197.     if ( NUM( w ) < NUM( pr->smallest ) ) {
  198.     pr->second = pr->smallest;
  199.     pr->smallest = w;
  200.     return TRUE;
  201.     }
  202.  
  203.     if ( w == pr->second )
  204.     return FALSE;
  205.  
  206.     if ( NUM( w ) < NUM( pr->second ) )
  207.     pr->second = w;
  208.  
  209.     return FALSE;
  210. }
  211.  
  212. /*
  213.  * correct the flow of control in the new program - use GOTO's which may
  214.  * be changed later to NEXT, BREAK, etc.
  215.  */
  216.  
  217. /* for these, control never flows directly to following statement */
  218. /* (also N_BREAK, N_CONTINUE, but these don't yet exist) */
  219. #define HASLEX(t) ( t != N_GOTO && t != N_ITER && t != N_END && t != N_CASE )
  220.  
  221. static
  222. fixflow( v, autolex )
  223. register int v;
  224. register int autolex;        /* lexical successor of v */
  225. {
  226.     register int lex, chlex, z, x, w;
  227.     register int i;
  228.  
  229.     if ( HASLEX( NTYPE(v) ) ) {
  230.  
  231.     lex = lexval( v, autolex );
  232.     if ( DEFINED(REACH(v)) && REACH(v) != lex )
  233.         insib( v, makebr( REACH(v) ) );
  234.     }
  235.  
  236.     if ( NTYPE(v) == N_ITER ) {
  237.     BRK(v) = autolex;
  238.     chlex = v;
  239.     } else {
  240.     chlex = lexval( v, autolex );
  241.     if ( NTYPE(v) == N_SWITCH )
  242.         BRK(v) = chlex;
  243.     }
  244.  
  245.     for ( i = 0; i < CHILDNUM(v); i++ ) {
  246.     w = LCHILD(v,i);
  247.  
  248.     if ( DEFINED(w) )
  249.         fixflow( w, chlex );
  250.  
  251.     else {
  252.         z = ARC(v,i);
  253.  
  254.         if (z != chlex) {
  255.         x = makebr( z );
  256.         LCHILD(v,i) = x;
  257.         RSIB(x) = NONE;
  258.         }
  259.     }
  260.     }
  261.  
  262.     if ( DEFINED( RSIB(v) ) )
  263.     fixflow( RSIB(v), autolex );
  264. }
  265.  
  266. static int
  267. lexval( v, lastlex )
  268. register int v, lastlex;
  269. {
  270.     register int sib;
  271.  
  272.     if ( !HASLEX( NTYPE(v) ) )
  273.     return NONE;
  274.  
  275.     sib = RSIB(v);
  276.  
  277.     if ( !DEFINED(sib) )
  278.     return lastlex;
  279.  
  280.     else if ( NTYPE(sib) == N_GOTO )
  281.     return ARC(sib,0);
  282.     else
  283.     return sib;
  284. }
  285.  
  286. /* make branching node leading to w */
  287. static int
  288. makebr( w )
  289. register int w;
  290. {
  291.     register struct node *new;
  292.  
  293.     if ( node_count + 1 > node_max )
  294.     node_grow();
  295.  
  296.     new = get_node( 1 );
  297.     new->node_type = N_GOTO;
  298.     new->num_arcs = 1;
  299.     new->arcs[0] = w;
  300.     new->right_sibling = NONE;
  301.     new->reach = NONE;
  302.     node_array[node_count - 1] = new;
  303.     return node_count - 1;
  304. }
  305.  
  306. #define BRANCHTYPE(t) (t == N_GOTO || t == N_BREAK || t == N_CONTINUE || \
  307.                t == N_END)
  308. #define MAXCHUNK 100
  309.  
  310. /* if ELSE_ARC clause smaller than MAXCHUNK and smaller than THEN_ARC clause,
  311.  * and there is no reason not to negate the if, negate the if */
  312.  
  313. /* turn N_IF into THEN_ARC when appropriate, create ELSE_ARC ifs where
  314.  * possible  */
  315. static
  316. getthen( v )
  317. register int v;
  318. {
  319.     register int tch, fch;
  320.     register int tn,fn;
  321.     register int recvar;
  322.  
  323.     if ( NTYPE(v) == N_IF || NTYPE(v) == N_ORIF || NTYPE(v) == N_BRANCH ) {
  324.     tch = LCHILD(v,THEN_ARC);
  325.     fch = LCHILD(v,ELSE_ARC);
  326.  
  327.     if ( DEFINED(fch) ) {
  328.         if ( !DEFINED(tch) )
  329.         negate( v );
  330.         else if ( BRANCHTYPE( NTYPE(tch) ) )
  331.         mkthen( v );
  332.         else if ( BRANCHTYPE( NTYPE(fch) ) ) {
  333.         negate( v );
  334.         mkthen( v );
  335.         } else if ( ( NTYPE(fch) != N_IF && NTYPE(fch) != N_ORIF &&
  336.              NTYPE(fch) != N_BRANCH ) || DEFINED( RSIB(fch) ) )
  337.         if ( ( NTYPE(tch) == N_IF || NTYPE(tch) == N_ORIF
  338.               || NTYPE(tch) == N_BRANCH ) && !DEFINED( RSIB(tch) ) )
  339.             /* not an else if */
  340.             /* invert into else if */
  341.             negate( v );
  342.         else {
  343.             /* asoc(v,n) returns number of statements associated with v
  344.                if <= n, -1 otherwise */
  345.             tn = asoc( tch, MAXCHUNK );
  346.             fn = asoc( fch, MAXCHUNK );
  347.             if ( fn >= 0 && (tn < 0 || fn < tn) )
  348.             /* else clause smaller */
  349.             negate( v );
  350.         }
  351.     }
  352.     }
  353.  
  354.     for ( recvar = 0; recvar < CHILDNUM(v); recvar++ )
  355.     if ( DEFINED( LCHILD(v,recvar) ) )
  356.         getthen( LCHILD( v, recvar ) );
  357.  
  358.     if ( DEFINED( RSIB(v) ) )
  359.     getthen( RSIB(v) );
  360. }
  361.  
  362. static
  363. mkthen( v )
  364. register int v;
  365. {
  366.     register int w;
  367.  
  368.     w = LCHILD(v,ELSE_ARC);
  369.  
  370.     if ( DEFINED(w) ) {
  371.     insib( v, w );
  372.     LCHILD(v,ELSE_ARC) = NONE;
  373.     }
  374. }
  375.  
  376. static
  377. negate( v )
  378. register int v;
  379. {
  380.     register int temp;
  381.  
  382.     temp = LCHILD(v,THEN_ARC);
  383.     LCHILD(v,THEN_ARC) = LCHILD(v,ELSE_ARC);
  384.     LCHILD(v,ELSE_ARC) = temp;
  385.     NEG(v) = !NEG(v);
  386. }
  387.  
  388. #define ARCCOUNT(v)    REACH(v)
  389.  
  390. static
  391. fixhd( v, hd )
  392. register int v, hd;
  393. {
  394.     register int w, newhd;
  395.     register int i;
  396.  
  397.     head[v] = hd;
  398.     newhd = ( NTYPE(v) == N_ITER || NTYPE(v) == N_SWITCH ) ? v : hd;
  399.  
  400.     for ( i = 0; i < CHILDNUM(v); i++ )
  401.     for ( w = LCHILD(v,i); DEFINED(w); w = RSIB(w) )
  402.         fixhd( w, newhd );
  403. }
  404.  
  405. static
  406. getloop()
  407. {
  408.     cntarcs();
  409.     fixloop( 0 );
  410. }
  411.  
  412. /* count arcs entering each node */
  413. static
  414. cntarcs()
  415. {
  416.     register int w,v;
  417.     register int i;
  418.  
  419.     for ( v = 0; v < node_count; v++ )
  420.     ARCCOUNT(v) = 0;
  421.  
  422.     for ( v = 0; v < node_count; v++ )
  423.     if ( NTYPE(v) != N_UNREACH && NTYPE(v) != N_GOTO &&
  424.         NTYPE(v) != N_SWITCH )
  425.         for ( i = 0; i < ARCNUM(v); i++ ) {
  426.         w = ARC(v,i);
  427.         if ( DEFINED(w) )
  428.             ARCCOUNT(w)++;
  429.         }
  430. }
  431.  
  432. /* find WHILE loops  */
  433. static
  434. fixloop( v )
  435. register int v;
  436. {
  437.     register int r;
  438.  
  439.     if ( NTYPE(v) == N_LOOP ) {
  440.     NXT(ARC(v,0)) = ARC(v,0);
  441.     if ( !getwh(v) )
  442.         getun( v );
  443.     }
  444.  
  445.     for ( r = 0; r < CHILDNUM(v); r++ )
  446.     if ( DEFINED( LCHILD(v,r) ) )
  447.         fixloop( LCHILD(v,r) );
  448.  
  449.     if ( DEFINED( RSIB(v) ) )
  450.     fixloop( RSIB(v) );
  451. }
  452.  
  453. static
  454. getwh( v )
  455. register int v;
  456. {
  457.     register int vchild, vgrand, vgreat;
  458.  
  459.     vchild = LCHILD(v,0);
  460.     vgrand = LCHILD(vchild,0);
  461.  
  462.     if ( !DEFINED(vgrand) || !( ( NTYPE(vgrand) == N_IF ||
  463.                  NTYPE(vgrand) == N_ORIF ) &&
  464.                    !DEFINED( LCHILD(vgrand,ELSE_ARC) ) ) )
  465.     return FALSE;
  466.  
  467.     vgreat = LCHILD(vgrand,THEN_ARC);
  468.     if ( DEFINED(vgreat) && NTYPE(vgreat) == N_GOTO &&
  469.     ARC(vgreat,0) == BRK(vchild) ) {
  470.  
  471.     /* turn into WHILE */
  472.     NTYPE(v) = N_WHILE;
  473.     NEG( vgrand ) = !NEG( vgrand );
  474.     LPRED( v ) = vgrand; 
  475.     LCHILD(vchild,0) = RSIB(vgrand);
  476.     RSIB(vgrand) = NONE;
  477.     return TRUE;
  478.     }
  479.     return FALSE;
  480. }
  481.  
  482. /* change loop to REPEAT UNTIL if possible */
  483. static
  484. getun(v)
  485. register int v;
  486. {
  487.     register int vchild, vgrand,  vgreat, before, ch;
  488.  
  489.     vchild = LCHILD(v,0);
  490.  
  491.     if ( ARCCOUNT(vchild) > 2 )
  492.     return FALSE;        /* loop can be iterated without passing
  493.                    through predicate of UNTIL */
  494.     vgrand = ARC(vchild,0);
  495.  
  496.     if ( !DEFINED(vgrand) )
  497.     return FALSE;
  498.  
  499.     for ( ch = vgrand,before = NONE; DEFINED( RSIB(ch) ); ch = RSIB(ch) )
  500.     before = ch;
  501.  
  502.     if ( ( ( NTYPE(ch) != N_IF && NTYPE(ch) != N_ORIF )
  503.        || DEFINED( LCHILD(ch,ELSE_ARC) ) ) )
  504.     return FALSE;
  505.  
  506.     vgreat = LCHILD(ch,THEN_ARC);
  507.  
  508.     if ( DEFINED(vgreat) && NTYPE(vgreat) == N_GOTO &&
  509.     ARC(vgreat,0) == BRK(vchild) ) {
  510.     /* create  UNTIL node */
  511.     NTYPE(v) = N_UNTIL;
  512.     NXT( vchild ) = ch;
  513.     NEG( ch ) = !NEG( ch );
  514.     LPRED( v ) = ch;
  515.     RSIB( before ) = NONE;
  516.     return TRUE;
  517.     }
  518.     return FALSE;
  519. }
  520.  
  521. static
  522. getbranch()
  523. {
  524.     register int v;
  525.  
  526.     for ( v = 0; v < node_count; v++ )
  527.     LABEL(v) = FALSE;
  528.  
  529.     for ( v = 0; DEFINED(v); v = RSIB(v) )
  530.     chkbranch( v );
  531. }
  532.  
  533. static
  534. chkbranch( v )
  535. register int v;
  536. {
  537.     register int w;
  538.     register int i;
  539.  
  540.     if ( NTYPE(v) == N_GOTO ) {
  541.  
  542.     w = head[v];
  543.     if ( DEFINED(w) ) {
  544.  
  545.         if ( ARC(v,0) == BRK(w) )
  546.         NTYPE(v) = N_BREAK;
  547.  
  548.         else if ( ARC(v,0) == NXT(w) )
  549.         NTYPE(v) = N_CONTINUE;
  550.     }
  551.  
  552.     if ( NTYPE(v) == N_GOTO )
  553.         LABEL( ARC(v,0) ) = TRUE;
  554.     }
  555.  
  556.     for ( i = 0; i < CHILDNUM(v); i++ )
  557.     for ( w = LCHILD(v,i); DEFINED(w); w = RSIB(w) )
  558.         chkbranch( w );
  559. }
  560.  
  561. /*
  562.  * make right_sibling[w] = v, and make
  563.  * right_sibling[ rightmost sibling of v ] = previous right_sibling[w]
  564.  */
  565. static
  566. insib( w, v )
  567. register int w, v;
  568. {
  569.     register int u, temp;
  570.  
  571.     temp = RSIB(w);
  572.     RSIB(w) = v;
  573.     for ( u = v; DEFINED( RSIB(u) ); u = RSIB(u) )
  574.     ;
  575.  
  576.     RSIB(u) = temp;
  577. }
  578.  
  579. /* return # of nodes associated with v if <= n, -1 otherwise */
  580. static
  581. asoc( v, n )
  582. register int v;
  583. register int n;
  584. {
  585.     register int count, i, temp;
  586.     register int w;
  587.  
  588.     i = node_array[v]->node_type;
  589.     if ( i == N_FLOW || i == N_IF || i == N_BRANCH || i == N_CASE ||
  590.     i == N_END )
  591.     count = node_array[v]->end_address - node_array[v]->start_address;
  592.     else
  593.     count = 1;
  594.  
  595.     for ( i = 0; i < CHILDNUM(v); ++i ) {
  596.     w = node_array[v]->child[i];
  597.     if ( !DEFINED(w) )
  598.         continue;
  599.  
  600.     temp = asoc( w, n-count );
  601.     if ( temp == -1 )
  602.         return -1;
  603.  
  604.     count += temp;
  605.     if ( count > n )
  606.         return -1;
  607.     }
  608.  
  609.     if ( DEFINED(node_array[v]->right_sibling) ) {
  610.     temp = asoc( node_array[v]->right_sibling, n - count );
  611.     if ( temp == -1 )
  612.         return -1;
  613.     count += temp;
  614.     }
  615.  
  616.     if ( count > n )
  617.     return -1;
  618.     else
  619.     return count;
  620. }
  621.